package leetcode.l0529;

import leetcode.l0527.Easy_相交链表_160;

import java.util.Stack;

/**
 * @author Retain
 * @date 2021/5/29 10:21
 */
public class Easy_反转链表_206 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        reverseList(node1);
    }

    /**
     * 用栈实现
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        // 连接各结点
        ListNode newHead = null;
        // 记录首节点
        ListNode first = null;
        while (!stack.isEmpty()) {
            ListNode pop = stack.pop();
            // 第一个节点
            if (newHead == null) {
                newHead = pop;
                first = newHead;
            }else {
                newHead.next = pop;
                newHead = newHead.next;
            }
            // 将原链表节点的next置为null，否则会出现循环
            pop.next = null;
        }
        return  first;
    }

    static class ListNode {
            int val;
            ListNode next;
            ListNode(int x) {
                val = x;
            next = null;
        }
    }
}
